import java.util.Scanner;

class Solution {
    //目标和
    public int findTargetSumWays(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        //预处理
        for(int i = 0; i < n; i++){
            sum += nums[i];
        }
        int a = (sum + target) / 2;
        if(a < 0 || (sum + target) % 2 == 1) return 0;

        //创建dp表
        int[][] dp = new int[n + 1][a + 1];
        //初始化
        dp[0][0] = 1;
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= a; j++){
                dp[i][j] = dp[i - 1][j];
                if(j - nums[i - 1] >= 0) dp[i][j] += dp[i - 1][j - nums[i - 1]];
            }
        }
        //返回
        return dp[n][a];
    }
    //目标和(空间优化)
    public int findTargetSumWays2(int[] nums, int target) {
        int n = nums.length;
        int sum = 0;
        //预处理
        for(int i = 0; i < n; i++){
            sum += nums[i];
        }
        int a = (sum + target) / 2;
        if(a < 0 || (sum + target) % 2 == 1) return 0;
        //创建dp表
        int[] dp = new int[a + 1];
        //初始化
        dp[0] = 1;
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = a; j >= 0; j--){
                if(j - nums[i - 1] >= 0) dp[j] += dp[j - nums[i - 1]];
            }
        }
        //返回
        return dp[a];
    }
    //最后一块石头的重量II
    public int lastStoneWeightII(int[] stones) {
        int n = stones.length;
        int sum = 0;
        //预处理
        for(int x: stones) sum += x;
        int a = sum / 2;
        //创建dp表
        int[][] dp = new int[n + 1][a + 1];
        //初始化
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= a; j++){
                dp[i][j] = dp[i - 1][j];
                if(j - stones[i - 1] >= 0) dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
            }
        }
        //返回
        return sum - 2*dp[n][a];
    }
    //最后一块石头的重量II优化
    public int lastStoneWeightII2(int[] stones) {
        int n = stones.length;
        int sum = 0;
        //预处理
        for(int x: stones) sum += x;
        int a = sum / 2;
        //创建dp表
        int[] dp = new int[a + 1];
        //初始化
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = a; j >= 0; j--){
                if(j - stones[i - 1] >= 0) dp[j] = Math.max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
            }
        }
        //返回
        return sum - 2*dp[a];
    }

    //完全背包
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int V = in.nextInt();
        int[] v = new int[n + 1];
        int[] w = new int[n + 1];
        for(int i = 1; i <= n; i++){
            v[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        //问题1
        //创建dp表
        int[][] dp = new int[n + 1][V + 1];
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= V; j++){
                dp[i][j] = dp[i - 1][j];
                if(j - v[i] >= 0) dp[i][j] = Math.max(dp[i][j],
                        dp[i][j - v[i]] + w[i]);
            }
        }
        //返回
        System.out.println(dp[n][V]);

        //问题2
        //创建dp表
        int[][] dp2 = new int[n + 1][V + 1];
        //初始化
        for(int j = 1; j <= V; j++){
            dp[0][j] = -1;
        }
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= V; j++){
                dp[i][j] = dp[i - 1][j];
                if(j - v[i] >= 0 && dp[i][j - v[i]] != -1){
                    dp[i][j] = Math.max(dp[i][j], dp[i][j - v[i]] + w[i]);
                }
            }
        }
        dp[n][V] = dp[n][V] >= 0 ? dp[n][V] : 0;
        System.out.println(dp[n][V]);
    }
    //零钱兑换
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        //创建dp表
        int[] dp = new int[amount + 1];
        int INF = 0x3f3f3f3f;
        //初始化
        for(int j = 1; j <= amount; j++) dp[j] = INF;
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= amount; j++){
                if(j - coins[i - 1] >= 0)
                    dp[j] = Math.min(dp[j], dp[j - coins[i - 1]] + 1);
            }
        }
        //返回
        dp[amount] = dp[amount] >= INF ? -1 : dp[amount];
        return dp[amount];
    }

    //零钱兑换II
    public int change(int amount, int[] coins) {
        int n = coins.length;
        //创建dp表
        int[] dp = new int[amount + 1];
        //初始化
        dp[0] = 1;
        //填表
        for(int i = 1; i <= n; i++){
            for(int j = 0; j <= amount; j++){
                if(j - coins[i - 1] >= 0) dp[j] += dp[j - coins[i - 1]];
            }
        }
        //返回
        return dp[amount];
    }
    //完全平方数
    public int numSquares(int n) {
        //创建dp表
        int[] dp = new int[n + 1];
        int INF = 0x3f3f3f3f;
        for(int j = 1; j <= n; j++) dp[j] = INF;
        for(int i = 1; i * i <= n; i++){
            for(int j = 0; j <= n; j++){
                if(j - i * i >= 0)
                    dp[j] = Math.min(dp[j], dp[j - i * i] + 1);
            }
        }
        return dp[n];
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {7,9,3,8,0,2,4,8,3,9};
        solution.findTargetSumWays(nums, 3);
    }
}